home *** CD-ROM | disk | FTP | other *** search
/ Aminet 2 / Aminet AMIGA CDROM (1994)(Walnut Creek)[Feb 1994][W.O. 44790-1].iso / Aminet / util / gnu / groff_src.lha / Groff-1.07 / troff / symbol.cc < prev    next >
C/C++ Source or Header  |  1992-11-25  |  4KB  |  145 lines
  1. // -*- C++ -*-
  2. /* Copyright (C) 1989, 1990, 1991, 1992 Free Software Foundation, Inc.
  3.      Written by James Clark (jjc@jclark.com)
  4.  
  5. This file is part of groff.
  6.  
  7. groff is free software; you can redistribute it and/or modify it under
  8. the terms of the GNU General Public License as published by the Free
  9. Software Foundation; either version 2, or (at your option) any later
  10. version.
  11.  
  12. groff is distributed in the hope that it will be useful, but WITHOUT ANY
  13. WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14. FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15. for more details.
  16.  
  17. You should have received a copy of the GNU General Public License along
  18. with groff; see the file COPYING.  If not, write to the Free Software
  19. Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
  20.  
  21.  
  22. #include "troff.h"
  23. #include "symbol.h"
  24.  
  25. const char **symbol::table = 0;
  26. int symbol::table_used = 0;
  27. int symbol::table_size = 0;
  28. char *symbol::block = 0;
  29. int symbol::block_size = 0;
  30.  
  31. const symbol NULL_SYMBOL;
  32.  
  33. #ifdef BLOCK_SIZE
  34. #undef BLOCK_SIZE
  35. #endif
  36.  
  37. const int BLOCK_SIZE = 1024;
  38. // the table will increase in size as necessary
  39. // the size will be chosen from the following array
  40. // add some more if you want
  41. // I think it unlikely that we'll need more than a million symbols
  42. static const unsigned int table_sizes[] = { 
  43. 101, 503, 1009, 2003, 3001, 4001, 5003, 10007, 20011, 40009, 80021, 160001, 500009, 1000003, 0 
  44. };
  45. const double FULL_MAX = 0.3;    // don't let the table get more than this full
  46.  
  47. static unsigned int hash_string(const char *p)
  48. {
  49.   // compute a hash code; this assumes 32-bit unsigned ints
  50.   // see p436 of  Compilers by Aho, Sethi & Ullman
  51.   // give special treatment to two-character names
  52.   unsigned int hc = 0, g;
  53.   if (*p != 0) {
  54.     hc = *p++;
  55.     if (*p != 0) {
  56.       hc <<= 7;
  57.       hc += *p++;
  58.       for (; *p != 0; p++) {
  59.     hc <<= 4;
  60.     hc += *p;
  61.     if ((g = (hc & 0xf0000000)) == 0) {
  62.       hc ^= g >> 24;
  63.       hc ^= g;
  64.     }
  65.       }
  66.     }
  67.   }
  68.   return hc;
  69. }
  70.  
  71. symbol::symbol(const char *p, int how)
  72. {
  73.   if (p == 0 || *p == 0) {
  74.     s = 0;
  75.     return;
  76.   }
  77.   if (table == 0) {
  78.     table_size = table_sizes[0];
  79.     table = (const char **)new char*[table_size];
  80.     for (int i = 0; i < table_size; i++)
  81.       table[i] = 0;
  82.     table_used = 0;
  83.   }
  84.   unsigned int hc = hash_string(p);
  85.   for (const char **pp  = table + hc % table_size; 
  86.        *pp != 0; 
  87.        (pp == table ? pp = table + table_size - 1 : --pp))
  88.     if (strcmp(p, *pp) == 0) {
  89.       s = *pp;
  90.       return;
  91.     }
  92.   if (how == MUST_ALREADY_EXIST) {
  93.     s = 0;
  94.     return;
  95.   }
  96.   if (table_used  >= table_size - 1 || table_used >= table_size*FULL_MAX) {
  97.     const char **old_table = table;
  98.     unsigned int old_table_size = table_size;
  99.     for (int i = 1; table_sizes[i] <= old_table_size; i++)
  100.       if (table_sizes[i] == 0)
  101.     fatal("too many symbols");
  102.     table_size = table_sizes[i];
  103.     table_used = 0;
  104.     table = (const char **)new char*[table_size];
  105.     for (i = 0; i < table_size; i++)
  106.       table[i] = 0;
  107.     for (pp = old_table + old_table_size - 1; 
  108.      pp >= old_table;
  109.      --pp) {
  110.        symbol temp(*pp, 1); /* insert it into the new table */
  111.      }
  112.     a_delete old_table;
  113.     for (pp = table + hc % table_size;
  114.      *pp != 0; 
  115.      (pp == table ? pp = table + table_size - 1 : --pp))
  116.       ;
  117.   }
  118.   ++table_used;
  119.   if (how == DONT_STORE) {
  120.     s = *pp = p;
  121.   }
  122.   else {
  123.     int len = strlen(p)+1;
  124.     if (block == 0 || block_size < len) {
  125.       block_size = len > BLOCK_SIZE ? len : BLOCK_SIZE;
  126.       block = new char [block_size];
  127.     }
  128.     (void)strcpy(block, p);
  129.     s = *pp = block;
  130.     block += len;
  131.     block_size -= len;
  132.   }
  133. }
  134.  
  135. symbol concat(symbol s1, symbol s2)
  136. {
  137.   char *buf = new char [strlen(s1.contents()) + strlen(s2.contents()) + 1];
  138.   strcpy(buf, s1.contents());
  139.   strcat(buf, s2.contents());
  140.   symbol res(buf);
  141.   a_delete buf;
  142.   return res;
  143. }
  144.  
  145.